There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.
The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.
Example 1:
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean
[0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean
[1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean
[1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean
[2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean
[3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean
[3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean
[4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.
Example 2:
Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.
Constraints:
m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 10^5
xianyu
#include <stdlib.h>
#include <stdbool.h>
// 比較函數，用於排序用
#define max(a, b) ((a) > (b) ? (a) : (b))
// DFS，用來標記能流向指定海洋的格子
void dfs(int** heights, int heightsSize, int* heightsColSize, int r, int c, bool** ocean, int prevHeight) {
// 如果座標超出邊界或格子高度低於前一個格子，則停止搜尋
if (r < 0 || r >= heightsSize || c < 0 || c >= heightsColSize[r] || ocean[r][c] || heights[r][c] < prevHeight) {
return; // 結束此路徑的搜尋
}
ocean[r][c] = true; // 標記當前格子為可達到的格子
// 往四個方向進行DFS搜尋
dfs(heights, heightsSize, heightsColSize, r + 1, c, ocean, heights[r][c]); // 下
dfs(heights, heightsSize, heightsColSize, r - 1, c, ocean, heights[r][c]); // 上
dfs(heights, heightsSize, heightsColSize, r, c + 1, ocean, heights[r][c]); // 右
dfs(heights, heightsSize, heightsColSize, r, c - 1, ocean, heights[r][c]); // 左
}
// 返回能同時流向太平洋和大西洋的格子座標。
//注意：返回的結果和*returnColumnSizes的陣列都必須是malloc分配
int** pacificAtlantic(int** heights, int heightsSize, int* heightsColSize, int* returnSize, int** returnColumnSizes) {
// 檢查輸入是否為空
if (heightsSize == 0 || heightsColSize[0] == 0) {
*returnSize = 0; // 設定返回大小為0
return NULL; // 返回空 pointer
}
int m = heightsSize; // 行數
int n = heightsColSize[0]; // 列數
// 分配兩個boolean matrix，用來標記能流向太平洋和大西洋的格子
bool** pacific = (bool**)malloc(m * sizeof(bool*)); // 太平洋布林矩陣
bool** atlantic = (bool**)malloc(m * sizeof(bool*)); // 大西洋布林矩陣
for (int i = 0; i < m; i++) {
pacific[i] = (bool*)calloc(n, sizeof(bool)); // 初始化為false
atlantic[i] = (bool*)calloc(n, sizeof(bool)); // 初始化為false
}
// 從邊界開始進行DFS
for (int i = 0; i < m; i++) {
dfs(heights, heightsSize, heightsColSize, i, 0, pacific, heights[i][0]); // 太平洋左邊界
dfs(heights, heightsSize, heightsColSize, i, n - 1, atlantic, heights[i][n - 1]); // 大西洋右邊界
}
for (int j = 0; j < n; j++) {
dfs(heights, heightsSize, heightsColSize, 0, j, pacific, heights[0][j]); // 太平洋上邊界
dfs(heights, heightsSize, heightsColSize, m - 1, j, atlantic, heights[m - 1][j]); // 大西洋下邊界
}
// 找出同時能流向太平洋和大西洋的格子
int** result = (int**)malloc(m * n * sizeof(int*)); // 分配結果陣列
*returnColumnSizes = (int*)malloc(m * n * sizeof(int)); // 分配列大小陣列
*returnSize = 0; // 初始化返回大小為0
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 如果格子能同時流向太平洋和大西洋
if (pacific[i][j] && atlantic[i][j]) {
result[*returnSize] = (int*)malloc(2 * sizeof(int)); // 分配座標空間
result[*returnSize][0] = i; // 設定行座標
result[*returnSize][1] = j; // 設定列座標
(*returnColumnSizes)[*returnSize] = 2; // 設定列大小為2
(*returnSize)++; // 增加返回大小
}
}
}
// 釋放boolean matrix memory
for (int i = 0; i < m; i++) {
free(pacific[i]); // 釋放太平洋矩陣的memory
free(atlantic[i]); // 釋放大西洋矩陣的memory
}
free(pacific); // 釋放太平洋指標的memory
free(atlantic); // 釋放大西洋指標的memory
return result; // 返回結果陣列
}
#include <stdlib.h>
#include <stdbool.h>
// 比較函數，用於排序用
#define max(a, b) ((a) > (b) ? (a) : (b))
// DFS，用來標記能流向指定海洋的格子
void dfs(int** heights, int heightsSize, int* heightsColSize, int r, int c, bool** ocean, int prevHeight) {
// 如果座標超出邊界或格子高度低於前一個格子，則停止搜尋
if (r < 0 || r >= heightsSize || c < 0 || c >= heightsColSize[r] || ocean[r][c] || heights[r][c] < prevHeight) {
return; // 結束此路徑的搜尋
}
ocean[r][c] = true; // 標記當前格子為可達到的格子
// 往四個方向進行DFS搜尋
dfs(heights, heightsSize, heightsColSize, r + 1, c, ocean, heights[r][c]); // 下
dfs(heights, heightsSize, heightsColSize, r - 1, c, ocean, heights[r][c]); // 上
dfs(heights, heightsSize, heightsColSize, r, c + 1, ocean, heights[r][c]); // 右
dfs(heights, heightsSize, heightsColSize, r, c - 1, ocean, heights[r][c]); // 左
}
// 返回能同時流向太平洋和大西洋的格子座標。
//注意：返回的結果和*returnColumnSizes的陣列都必須是malloc分配
int** pacificAtlantic(int** heights, int heightsSize, int* heightsColSize, int* returnSize, int** returnColumnSizes) {
// 檢查輸入是否為空
if (heightsSize == 0 || heightsColSize[0] == 0) {
*returnSize = 0; // 設定返回大小為0
return NULL; // 返回空 pointer
}
int m = heightsSize; // 行數
int n = heightsColSize[0]; // 列數
// 分配兩個boolean matrix，用來標記能流向太平洋和大西洋的格子
bool** pacific = (bool**)malloc(m * sizeof(bool*)); // 太平洋布林矩陣
bool** atlantic = (bool**)malloc(m * sizeof(bool*)); // 大西洋布林矩陣
for (int i = 0; i < m; i++) {
pacific[i] = (bool*)calloc(n, sizeof(bool)); // 初始化為false
atlantic[i] = (bool*)calloc(n, sizeof(bool)); // 初始化為false
}
// 從邊界開始進行DFS
for (int i = 0; i < m; i++) {
dfs(heights, heightsSize, heightsColSize, i, 0, pacific, heights[i][0]); // 太平洋左邊界
dfs(heights, heightsSize, heightsColSize, i, n - 1, atlantic, heights[i][n - 1]); // 大西洋右邊界
}
for (int j = 0; j < n; j++) {
dfs(heights, heightsSize, heightsColSize, 0, j, pacific, heights[0][j]); // 太平洋上邊界
dfs(heights, heightsSize, heightsColSize, m - 1, j, atlantic, heights[m - 1][j]); // 大西洋下邊界
}
// 找出同時能流向太平洋和大西洋的格子
int** result = (int**)malloc(m * n * sizeof(int*)); // 分配結果陣列
*returnColumnSizes = (int*)malloc(m * n * sizeof(int)); // 分配列大小陣列
*returnSize = 0; // 初始化返回大小為0
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 如果格子能同時流向太平洋和大西洋
if (pacific[i][j] && atlantic[i][j]) {
result[*returnSize] = (int*)malloc(2 * sizeof(int)); // 分配座標空間
result[*returnSize][0] = i; // 設定行座標
result[*returnSize][1] = j; // 設定列座標
(*returnColumnSizes)[*returnSize] = 2; // 設定列大小為2
(*returnSize)++; // 增加返回大小
}
}
}
// 釋放boolean matrix memory
for (int i = 0; i < m; i++) {
free(pacific[i]); // 釋放太平洋矩陣的memory
free(atlantic[i]); // 釋放大西洋矩陣的memory
}
free(pacific); // 釋放太平洋指標的memory
free(atlantic); // 釋放大西洋指標的memory
return result; // 返回結果陣列
}
// 測試函數
void testPacificAtlantic() {
// 測試用的矩陣
int testHeights[5][5] = {
{1, 2, 2, 3, 5},
{3, 2, 3, 4, 4},
{2, 4, 5, 3, 1},
{6, 7, 1, 4, 5},
{5, 1, 1, 2, 4}
};
int heightsSize = 5; // 行數
int heightsColSize[5] = {5, 5, 5, 5, 5}; // 每行的列數
// 將2D陣列轉成指標陣列
int* heights[5];
for (int i = 0; i < heightsSize; i++) {
heights[i] = testHeights[i];
}
// 定義返回變數
int returnSize;
int* returnColumnSizes;
// 呼叫pacificAtlantic函數
int** result = pacificAtlantic(heights, heightsSize, heightsColSize, &returnSize, &returnColumnSizes);
// 印出結果
printf("同時能流向太平洋和大西洋的格子座標：\n");
for (int i = 0; i < returnSize; i++) {
printf("[%d, %d]\n", result[i][0], result[i][1]);
free(result[i]); // 釋放結果陣列的記憶體
}
free(result); // 釋放結果陣列的指標
free(returnColumnSizes); // 釋放列大小的記憶體
}
int main() {
testPacificAtlantic();
return 0;
}
```-
iThome鐵人賽
看影片追技術